\documentclass[10pt, a4paper, titlepage]{article}
\usepackage[utf8]{inputenc}
\usepackage[francais]{babel}
\usepackage[T1]{fontenc}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{graphicx}
\newcommand{\HRule}{\rule{\linewidth}{0.5mm}}

%\title{Gestion distribuée de l'accès à un parking\\
%Algorithmique distribuée}
%\author{Ronnie Muthada Pottayya \and Sophie Teixeira}
%\date{13 novembre 2013}

\begin{document}
%\maketitle
\input{titlepage2.tex}

% \clearpage

\tableofcontents

\clearpage

\section{Introduction}

Ce projet réalise la gestion de l'accès à un parking. Un parking peut posséder une ou plusieurs portes par lesquelles des véhicules peuvent entrer ou sortir. Dans le cas où nous avons une seule porte, le problème ne semble pas compliqué. Mais lorsque nous avons plusieurs portes, elles doivent communiquer entre elles afin de toutes avoir des états cohérents. Par exemple, si dans un parking nous n'avons aucune place disponible et que nous avons 3 portes, lors de la sortie d'une voiture, les trois portes doivent être au courant de cette sortie et donc que dans le parking il y a une place disponible. C'est là où intervient le domaine de l'algorithmique distribuée qui est de faire en sorte que plusieurs processus dans un seul et même système communiquent entre eux afin d'avoir tous des états cohérents.

\medskip
Notre parking dispose de $N$ places de stationnement et de $P$ portes par lesquelles les voitures peuvent entrer et sortir. Le but de ce projet est donc de simuler la gestion de ce parking en garantissant qu'aucune voiture ne rentre si elle n'y pas de place pour se garer. La bonne gestion des entrées et des sorties sera garantie par un algorithme distribué qui réalisera la synchronisation entre les portes en exécutant toutes le même algorithme. 


\section{Structure du projet}

Le projet est divisé en cinq packages dont deux principaux. Chaque protocole que nous avons implémenté possède son propre sous package. Nous avons ensuite un package où sont définis différentes classes qui sont utilisées pour la définition des portes,un utilitaire nous permettant d'écrire dans un log les traces d'exécution du programme,  enfin le serveur de voiture et les trois packages des algorithmes. Finalement, nous avons un package qui gère la communication entre toutes les portes.

Un diagramme de classe simplifié est présenté dans la figure \ref{classes}.

\begin{figure}	
	\includegraphics[scale=0.5]{../UML/Diagrammedeclasses.png}
	\caption{Diagramme de classes simplifié du projet}
	\label{classes}
\end{figure}


\subsection{Le package \texttt{parking}}

Dans ce package, nous pouvons trouver l'implémentation des classes de base, telles que la classe \texttt{Message} qui est un \emph{enum} représentant les différents types de messages qui peuvent être échangés entre nos portes. 

Nous y trouvons aussi la classe \texttt{Door} permettant de lancer une porte. Cette classe peut être lancée sur différentes machines. Elle implémente l'interface \texttt{IDoor} qui contient deux méthodes essentielles : \texttt{demandeEntreeParking()} et \texttt{demandeSortieParking()} qui sont appelées réciproquement quand une voiture demande à entrer ou sortie du parking.

Nous y trouvons le serveur de voitures, \texttt{ServeurVoitures}, qui simule les entrées ou sortie des voitures dans le parking ainsi que l'interface \texttt{IServeurVoitures} qui contient la fonction \texttt{enregistrerPorte()}.

L'utilitaire permettant d'écrire les traces d'exécution du programme par un système de log y est aussi défini.

\subsection{Le package \texttt{abcast}}

Il contient l'ensemble des classes utilisées par le protocole ABCast : a classe primaire implémentant le protocole abcast, une classe permettant l'envoi des messages de diffusion par un processus initiateur, une classe permettant l'envoi et la réception d'accusés de réceptions, une classe permettant l'envoi et la réception de diffusions finales par le processus initiateur, un gestionnaire de réception d'accusé de réception utilisé par un processus initiateur dans un groupe.

\subsection{Le package \texttt{carvalho}}

Il s'agit du package contenant les fichiers nécessaire au protocole Carvalho Roucairol. Une classe \texttt{Carvalho\_Roucairol} contient toutes les règles de l'algorithme. Et un objet nommé \texttt{RequestClock} représentant une requête y est défini pour la bonne exécution du protocole.

\subsection{Le package \texttt{naimi\_trehel}}

Le protocole Naimi Trehel y est défini dans ce package. Nous y trouvons aussi une classe nommée \texttt{Token} qui représente le jeton. 

\subsection{Le package \texttt{reso}}

Il s'agit de la définition du serveur qui gère les envois et réceptions de messages entre les portes. Ce package nous a été fourni et n'a pas été modifié. Tous les messages échangés entre les portes transitent par \texttt{Reso}. Chaque utilisation introduit un temps de latence dans les envois de messages entre les portes.


\section{Description du projet}

\subsection{Fonctionnement global}

Nous avons la classe \texttt{ServeurVoiture} qui est responsable de la simulation d'entrée ou de sortie de voiture dans le parking. Cette classe, comme son nom l'indique, est un serveur, et implémente l'interface \texttt{IServeurVoitures}. Cette interface permet aux portes de s'enregistrer auprès du serveur de voitures. 

Ainsi, le serveur connaît les portes et peut donc simuler des demandes d'entrée ou de sortie auprès des portes. Les portes, quant à elles,  font appel à la méthode fournie par le serveur de voitures qui leur permet de s'enregistrer. 

\medskip
Les portes exécutent chacune le même algorithme. Pour cela, elles implémentent l'interface \texttt{IDoor}. En effet, une porte peut être vue comme étant un serveur. Nous avons donc là deux serveurs qui communiquent entre eux. Le serveur de voitures connaît donc l'objet de type interface représentant une porte. Ainsi, il est facile pour le serveur d'envoyer une demande d'entrée ou de sortie à une porte. Les portes exécutent toutes les mêmes algorithmes. Une interface permettant de regrouper tous les algorithmes à été créée. Dans cette interface, nous pouvons trouver deux méthodes : une pour une demande d'entrée et une pour une demande de sortie. De ce fait, tous les algorithmes donnent une implémentation de ces eux méthodes. A l'exécution d'une porte, le choix de l'algorithme est donné. En ce faisant, la demande d'exécution d'un algorithme est mieux structurée.

\subsubsection*{Communications RMI}
Le serveur de voitures, les portes et reso communiquent entre eux grâce aux Java RMI. Le premier serveur lancé est \texttt{Reso} grâce au \texttt{Launcher}. C'est lui qui se charge de créer le registre RMI puis de faire un \emph{rebind} sur \texttt{Reso}.

Ensuite le serveur de voitures est lancé et recherche le registre RMI précédemment créé. Il fait ensuite un \emph{rebind} sur celui-ci. L'utilisation de cette fonction ne pouvant se faire qu'en local, le serveur de voitures doit toujours être lancé sur la même machine que \texttt{Reso}.

Finalement, les portes sont lancées après ces deux serveurs. Elles font un \emph{lookup} sur le serveur de voitures pour recevoir les demandes d'entrée et de sortie ainsi qu'un \emph{lookup} sur \texttt{Reso} pour que les algorithmes puissent faire transiter les messages entre les portes.



\subsubsection*{Déroulement}
Le début du projet se déroule chronologiquement de la manière suivante :
\begin{center}

\begin{tabular}{| l | l | l |}
\hline
\texttt{Launcher}		&	\texttt{ServeurVoitures}	& \texttt{Door} \\
\hline
\hline
1. Lancé				&								&				\\
2. Crée registre RMI	&								&				\\
3. S'enregistre sur le 	&								&				\\
registre				&								&				\\
						& 4. Lancé						&				\\
						& 5. Trouve le registre			&				\\
						& 6. S'enregistre sur le 		&				\\
						& registre						&				\\
						& 7. Attend les portes  		&				\\
						&								& 8. Lancée \\
						&								& 9. Récupère registre sur \texttt{Reso} \\
						&								& 10. Crée Porte et algorithme\\
						&								& 11. Récupère registre sur\\
						&								&  \texttt{ServeurVoitures} \\
						&								& 12. Se déclare sur \\
						&								& \texttt{ServeurVoitures} \\
						&								& 13. Reçoit demande entrée/sortie \\
						&								& 14. Transmet demande à l'algo\\
						
\hline
\end{tabular}
\end{center}

L'algorithme fait ensuite les transmissions de messages entre les différentes portes et s'occupe de faire entrer ou sortir une voiture dans le parking lorsque cela est bien possible. Les étapes 13 et 14 peuvent se répéter ensuite à l'infini.

%TODO Le système de log
\subsubsection*{Le système de log}
Pour observer le déroulement de nos algorithmes mais surtout les échanges de entre chacune de nos portes, nous avons mis en place un système de fichiers de log.

Pour cela, nous avons utilisé l'API Java \texttt{Logging}. Cette dernière nous permet d'écrire dans un fichier spécifié à la création toutes les informations que nous trouvons importantes selon différents niveaux. Des messages peuvent ainsi être considérés comme information et d'autre comme configuration ou messages de debug. Nous pouvons grâce à cette API choisir quel niveau de messages est écrit dans le log ou non.


\subsection{Description technique du serveur de voitures}

Comme mentionné dans le chapitre précédent, le serveur de voitures simule les entrées ou sorties de voitures dans le parking. Ce serveur possède un compteur représentant le nombre de voitures à l'intérieur du parking. Il génère aléatoirement des entrées ou des sorties de voitures dans le parking. Toutefois, si le compteur interne du serveur indique qu'il n'y a aucune voiture dans le parking, qu'il est donc égal à zéro, le serveur garanti qu'une demande de sortie ne sera jamais faite. Le serveur connaît aussi le nombre de portes qui sont prêtes à recevoir des demandes d'entrée ou de sortie mais aussi le nombre de places disponibles dans le parking. Le nombre de places de parking total est primordial pour respecter la cohérence avec le nombre de places de parking disponibles.

\medskip
Nous avons fait le choix de dupliquer le serveur de voitures autant de fois qu'il y a de portes. Nous avons donc un fil d'exécution qui gère les entrées et sorties de voitures par portes. Ainsi, nous pouvons simuler simultanément des entrées ou des sorties de voitures sur plusieurs portes en même temps. Étant donné que tous les fils d'exécution partagent les compteurs, nous avons encapsulé ce compteur dans une classe et rendu cette classe \emph{thread-safe}. En faisant ainsi, les threads accèdent chacun leur tour à ce compteur. 

Autre point à souligner, le serveur ne lance pas de simulation si toutes les portes que nous lui avons attribuées au lancement ne sont pas connectées. Ceci est fait par une méthode \texttt{enregistrerPorte()} définie sur le serveur de voitures et dont les portes ont accès pour s'enregistrer auprès du serveur de voitures. A chaque enregistrement, une notification est envoyée au programme principal du serveur et tant que le nombre de portes enregistrées n'est pas égal au nombre de portes supposées être connectées le serveur de voitures attend (utilisation d'un mécanisme \emph{wait / notify}).



\subsection{Description technique d'une porte}
Chaque porte est représenté par un objet \texttt{Door}. Cet objet implémente l'interface \texttt{IDoor} comme dit précédemment, et implémente donc les fonctions de flux de voitures \texttt{demandeEntreeParking()} et \texttt{demandeSortieParking()}. Toutes les portes connaissent le nombre de places du parking à leur création et elles utilisent toutes le même algorithme pour la gestion des entrées et sorties.

Les portes contiennent donc une implémentation au choix d'un des algorithmes choisis, soit un algorithme de jeton, un algorithme d'horloge logique ou un algorithme de diffusion. Ce sont elles qui font appel à l'algorithme dès qu'une demande d'entrée ou de sortie d'une voiture dans le parking est faite.

%TODO more

\subsection{L'algorithme du jeton : Naimi-Trehel}

Naimi-Trehel est un algorithme qui introduit une structure arborescente dynamique, un jeton et une file virtuelle, représentée par un pointeur \texttt{next} indiquant le site successeur de $i$ dans la file d'attente. La complexité en nombre de messages pour cet algorithme est $O(log(n))$. L'algorithme se base sur $n$ portes qui vont vouloir accéder au parking. 

\medskip
Au démarrage, la porte ayant comme identifiant 0 est choisie comme étant la première à accéder au parking. Elle est aussi celle en possession du jeton. Toutes les autres portes connectées au système la considèrent comme leur père, ce qui crée un arbre avec la porte 0 comme racine et toutes les autres portes en feuilles. 
Lorsqu'une porte est en demande de section critique, donc d'entrée ou de sortie du parking, elle envoie à son père un message \texttt{REQ}. Si cette dernière ne possède pas de père, cela signifie qu'elle possède déjà le jeton, donc elle n'enverra pas de \texttt{REQ} à qui que ce soit et entrera directement en section critique. Dans le cas contraire, ce message sera transmis de fils en père jusqu'à ce que la porte détenant le jeton réceptionne la requête. Toutes les portes ayant été en contact avec ce message \texttt{REQ} mettent ainsi à jour leur père. C'est ainsi qu'au fil de l'exécution de l'algorithme les arbres sont modifiés dynamiquement. 

\medskip
Quand une porte $P_i$ reçoit une requête d'entrée en section critique (donc une demande d'entrée ou de sortie du parking) de la part de $P_j$, si elle possède le jeton et qu'elle n'est pas en section critique, alors elle envoie le jeton à $P_j$ et mets à jour sa variable \texttt{owner}. Par contre, si elle possède le jeton et qu'elle est en section critique, elle met à jour sa variable \texttt{next}. Dans le cas contraire, si elle ne possède pas le jeton et qu'elle n'a pas fait de demande de section critique, elle transmet la requête de $P_i$ à sa variable \texttt{owner}. Et si elle ne possède pas le jeton et qu'elle attend la section critique, elle enregistre la demande de $P_i$ dans sa variable \texttt{next}. Ainsi, si toutefois elle était demandeuse de section critique, quand elle sortira de section critique, elle enverra le jeton à \texttt{next} et sa variable \texttt{next} sera réinitialisée à \texttt{null}. 

\medskip
Pour l'implémentation de Naimi-Trehel, une classe \texttt{Token} représentant le jeton a été définie, et ce jeton est initialisé avec le nombre total de places de parking disponibles. Cela implique que lorsqu'une porte est en demande de section critique elle possède le jeton et selon le cas de la demande d'une voiture (entrée ou sortie), le nombre de places à l'intérieur du jeton se verra augmenté ou réduit de 1.


\subsubsection{Choix de l'algorithme utilisant un jeton}
Nous n'avons pas choisi Naimi-Trehel comme étant l'algorithme fonctionnant avec un jeton par hasard. En effet, cet algorithme détient plusieurs avantages par rapport aux autres algorithmes à base de jeton vu en cours. Parmi les algorithmes à base de jeton que nous avons vus, Le Lann ainsi que Suzuki et Kasami sont deux algorithmes moins performants que Naimi-Trehel. 

\medskip
Voyons les inconvénients de Le Lann. C'est un algorithme où nous avons les portes en topologie anneau avec un jeton circulant dans un seul sens, c'est à dire qu'une porte connaît son voisin et le voisin connaît son voisin. 

\medskip
Prenons un exemple avec un cas concret. Nous avons 4 portes numérotées 0, 1, 2, 3. La porte 0 connaît son voisin 1, 1 connaît 2, 2 connaît 3, et 3 connaît 0. Admettons que la porte 1 détienne le jeton. Si la porte 0 fait la demande de section critique tout de suite, elle devra attendre le passage du jeton par les portes 2 et 3 avant de recevoir le jeton. Il se pourrait que la porte 2 ait fait la demande d'entrée en section critique bien après la porte 0. Cela pose un problème dans la mesure où 0 était le premier à demander la section critique. 

\medskip
L'algorithme Le Lann garantit la sûreté et la vivacité mais ne garantit pas l'équité. Naimi-Trehel ne garantit pas l'équité non plus mais il est mieux dans la mesure où un processus peut faire la demande directement à celui qui détient le jeton. Si nous pouvons garantir une vitesse de transfert de données constante sur le réseau, Naimi-Trehel peut être équitable. 

\medskip
Dans le projet, l'équité n'est pas respectée. Étant donné que l'objet réseau introduit un temps de latence aléatoire. Cela signifie que si j'ai deux portes $a$ et $b$ qui font la demande de jeton ($a$ ayant demandé avant $b$) à celle qui possède le jeton, il se pourrait que $b$ détienne le jeton avant $a$ malgré le fait que $a$ ait fait la demande avant $b$ à cause du temps de latence introduit ($a$ avait un temps de latence supérieur à $b$). Ce problème est résolu avec des algorithmes à base d'estampilles que nous verrons dans les deux algorithmes qui suivent.

\medskip
Concernant l'algorithme de Suzuki et Kasami, nous n'avons pas choisi cet algorithme car Suzuki et Kasami fait plus d'échanges de messages. En effet, lorsqu'une porte veut accéder à la section critique, donc est en demande de jeton, elle envoie un message \texttt{REQ} à toutes les portes connectées au système. Seule la porte détenant le jeton lui répondra en lui envoyant le jeton. Il y a là un échange de messages supérieur à celui de Naimi-Trehel.


\subsection{L'algorithme de l'horloge logique : Carvalho et Roucairol}

Le second algorithme pour notre gestion de parking est un algorithme d'horloge logique, nous avons choisi d'implémenter l'algorithme de Carvalho et Roucairol. Cet algorithme fonctionne avec un système d'estampilles. Chaque processus, ici chaque porte, a sa propre horloge et à chaque envoi de message l'estampille est transportée de l'émetteur au récepteur.

\medskip
A l'initialisation de l'algorithme sur chacune des portes, nous initialisons l'estampille locale à 0 et nous récupérons la liste de toutes les portes voisines pour avoir la liste des voisins avec lesquels nous allons échanger des messages. L'initialisation se fait à la réception ou à l'envoi du premier message et non pas à la création de la porte, car il faut que toutes les portes soient déjà inscrites auprès du serveur de voitures pour récupérer la liste complète des voisins.

\medskip
Lorsqu'une porte reçoit une demande d'entrée ou de sortie, elle va demander à entrer en section critique. Pour cela elle va envoyer des requêtes à ses voisins auprès desquels elle attend une autorisation et attendre les réponses de chacun d'eux. L'objet \texttt{RequestClock} a été créé pour les envois de l'horloge logique. Il contient ici un message de type \texttt{REQ}, l'estampille de la demande d'entrée en section critique et le type de la demande (0 pour Entrée et 1 pour Sortie). Pour attendre que toutes les portes voisines aient répondu, nous avons mis en place un procédé de \emph{wait / notify}. Une fois que la porte a reçu une réponse de tous les voisins attendus, elle entre en section critique, ce qui consiste à laisser entrer ou sortir une voiture et donc décrémenter ou incrémenter le nombre de places libres dans son compteur local. 

Une fois que la porte a terminé la section critique, elle va accepter la libération de la section critique. Dans cette phase elle va envoyer un objet de type \texttt{RequestClock} contenant le message de type \texttt{REL} à tous ses voisins ainsi que le type de la section critique qui vient de se terminer (entrée / sortie). C'est grâce à ce procédé que nous tenons les compteurs locaux de toutes nos portes à jour.

\medskip
Lorsqu'une porte reçoit une requête de type \texttt{RequestClock}, nous regardons si cet objet contient un message de type \texttt{REL} ou \texttt{REQ}. 

Si le message est une demande d'acceptation d'entrée en section critique (\texttt{REQ}), elle commence par mettre à jour son estampille locale en prenant le maximum entre son estampille de demande de section critique locale et l'estampille reçue avec la requête en ajoutant 1. Ensuite, si elle n'est pas elle même en section critique, elle envoie un message \texttt{REL} au demandeur. Elle augmente également son compteur du nombre d'avis de libération attendus de 1. Si la porte est demandeuse de section critique, elle va envoyer un objet \texttt{RequestClock} avec le message \texttt{REQ} à la porte actuellement en demande de section critique pour lui signaler qu'elle souhaite prendre la section critique par la suite.

Si le message dans le \texttt{RequestClock} est une demande de permission (type \texttt{REL}) c'est que la porte qui a envoyé ce message vient de sortir de section critique. Nous récupérons donc le type de la section critique pour mettre à jour le compteur de places libres local. Nous faisons ensuite appel à la fonction d'acceptation du message \texttt{REL} si la porte n'est pas elle même demandeuse de section critique.

\medskip
Quand une porte reçoit un message de type \texttt{REL}, elle diminue son compteur du nombre d'avis de libération attendus et envoi un \texttt{notify()}, c'est ce qui permettra de sortir du \texttt{wait} de l'attente des réponses dans la fonction de demande de section critique.


\subsubsection*{Les messages dans le fichier de log}
Pour écrire les échanges s'effectuant entre nos portes, nous avons suivi un schéma simple. 

Par exemple pour l'envoi d'une requête de la porte 0 vers la porte 1 pour une demande d'entrée en section critique pour l'entrée d'une voiture, nous avons : \\
\texttt{Envoie : 0 -> 1 | REQ | entrée | H = 1}\\
Nous spécifions donc si le message est envoyé ou reçu, la porte émettrice puis la porte réceptrice, le type du message envoyé, s'il s'agit d'une entrée ou une sortie de voiture et enfin l'estampille de la porte.

\medskip
Lorsqu'une porte envoie un message \texttt{REL} mais en demandant une mise à jour du nombre de places libres dans la porte réceptrice, nous avons le message suivant :\\
\texttt{Envoie : 0 -> 1 | REL + UPDATE | entrée | H = 1}\\
Ce message contient le numéro de la porte émettrice suivi du numéro de la porte réceptrice, le type du message, le type de mise à jour du nombre de places à faire et l'estampille.

\medskip
Quand une porte reçoit un message de type \texttt{REL} avec une demande de mise à jour, le message se présente de la forme suivante : \texttt{Reçoit : 2 -> 0 | REL + UPDATE | Entrée | places libres = 1}\\
Il contient toujours le numéro de la porte émettrice puis celui de la porte réceptrice, le type du message, le type du mouvement de voiture et enfin le nombre de places libres dans le parking après la mise à jour de la variable locale.

\medskip
Finalement, quand une porte reçoit un simple message \texttt{REL}, il ne contient pour information que le numéro de la porte réceptrice et le type du message : \\
\texttt{Reçoit : 0 | REL}

\subsubsection*{Trace d'exécution commentée}
Une trace d'exécution commentée mettant évidence la gestion de concurrence pour cet algorithme est en annexe \ref{CR_log}.


\subsection{L'algorithme de diffusion : ABCast}

Pour l'implémentation du protocole ABCast, cinq différentes classes ont été créées. Ces cinq classes sont :
\begin{itemize}
	\item \texttt{ABCast} : elle définit le protocole ABCast
	\item \texttt{MessageAcknowledgment} : elle permet, pour un message de diffusion donné, de représenter l'accusé de réception. Cet objet est utilisé par les portes pour envoyer un accusé de réception à l'initiateur du message.
	\item \texttt{MessageDiffusion} : elle représente la diffusion d'un message au sein d'un groupe. Elle est utilisée par l'initiateur d'un message pour la diffusion de celui-ci au sein du groupe.
	\item \texttt{MessageFinalDiffusion}: elle représente la diffusion finale qu'envoie l'initiateur à tous les membres du groupe.
	\item \texttt{RetourAck} : classe utilisée par l'initiateur pour stocker pour un message les accusés de réception reçus.
\end{itemize}

\medskip
Le principe de l'ABCast est simple et efficace. Pour expliquer son fonctionnement et son adaptation au projet, nous allons prendre un exemple. Supposons qu'on a une porte qui fait une demande d'entrée en section critique, la première chose qu'elle va faire est d'instancier un objet de type \texttt{MessageDiffusion} avec son estampille locale, son identité, et le type de requête demandée (à pour entrée, 1 pour sortie). L'objet \texttt{MessageDiffusion}  va concaténer son estampille locale et son numéro de processus (exemple 3.1 avec 3 comme estampille locale et 1 identité de la porte initiatrice du message), et cette valeur réelle sera stockée dans l'objet. Le message aura aussi comme identité cette valeur concaténée. L'objet \texttt{MessageDiffusion} correspond au message qui sera diffusé. La porte incrémente ensuite son estampille locale et diffuse son objet \texttt{MessageDiffusion} à tous les membres du groupe. Après cela, la porte initiatrice stocke dans un tableau dynamique un objet de type \texttt{RetourAck}. Cet objet est instancié avec l'identité du message (l'identité du message est unique au système) et cet objet possède un tableau dynamique permettant de stocker les accusés de réception reçus des membres du groupe. 

\medskip
A la réception d'un message de type \texttt{MessageDiffusion}, une porte incrémente sa propre estampille locale, la concatène avec son identité (exemple 5.3 : 5 étant l'estampille locale de la porte ayant reçu le message de diffusion et 3 son identité), instancie un objet de type \texttt{MessageAcknowledgment} avec ce nouveau réel et l'identité du message reçu et l'envoie à l'initiateur du message. La porte ayant reçu le message de diffusion stockera cet objet dans une liste et le message est marqué comme \texttt{PENDING}. Cette liste est triée en ordre croissant de réel estampille.idProcessus. 
A chaque fois qu'un message apparaît en début de liste ayant la plus petite valeur estampille.idProcessus et ayant comme statut \texttt{READY}, le message est délivré par la porte et le message peut traiter ce message si c'est une entrée ou une sortie de voiture.

\medskip
L'initiateur du message recevra tous les accusés de réception des membres du groupe, qu'il stockera dans le tableau de l'objet \texttt{RetourAck}, qu'il avait précédemment instancié avec l'identifiant du message. Lorsqu'il aura reçu tous les accusés de réception, il choisira parmi eux celui ayant la plus grande valeur estampille.id processus et instanciera un objet de type \texttt{MessageFinalDiffusion} avec cette valeur choisie et l'identité du message de diffusion. Elle diffusera une deuxième fois ce message. A la réception de ce message de type  \texttt{MessageFinalDiffusion}, une porte mettra à jour la nouvelle valeur estampille.id processus reçue pour un message donné, précédemment stocké dans une liste de messages reçus, et ce message se verra changé de statut de \texttt{PENDING} en \texttt{READY}.  Cette liste est ensuite triée en fonction des valeurs estampille.idProcessus et s'il y a un message en début de liste avec le statut \texttt{READY}, alors il est délivré et traité selon si c'est une demande d'entrée ou de sortie de voiture. Le message est ensuite effacé de la liste des messages reçus.

\medskip
La classe \texttt{ABCast} donne une définition des deux méthodes de la interface \texttt{IAlgorithm}. En effet, à chaque appel de l'une de ces méthodes, un thread est lancé. Ceci étant fait afin que l'exécution de l'algorithme soit plus rapide. En effet, étant donné que notre serveur de voiture à été implémenté avec des fils d'exécution, cela implique que pour une porte, nous pouvons avoir deux entrées l'une après l'autre. En créant des fils d'exécution dynamiquement à chaque appel de la méthode \texttt{demandeEntree} ou de la méthode \texttt{demandeSortie}, cela veut dire que le premier appel de \texttt{demandeEntree} fera appel à la méthode \texttt{envoiDiffusionGroupe}. Cette méthode étant synchronisée, la deuxième entrée de voiture devra attendre la fin d'exécution de cette méthode de la première entrée. Lorsque la première entrée aura fini l'exécution de la méthode \texttt{envoiDiffusiongroupe}, la deuxième entrée pourra commencer l'exécution de cette méthode. A préciser qu'aucune des deux voitures ne rentrera dans le parking si le message de diffusion final n'a pas encore été reçu.

\medskip
L'avantage d'utiliser les fils d'exécutions dans cet algorithme est que pendant que la première demande d'entrée a commencé à recevoir des accusés de réception, la deuxième entrée peut commencer en même temps à envoyer ses messages de diffusion. Un point important à souligner est que les deux entrées ont la liste des messages partagée, donc l'utilisation de cette liste doit être \emph{thread-safe} et dans l'algorithme ce problème est pris en compte, et de toute façon, toutes les méthodes sont synchronisées.

\medskip
Le protocole ABCast nous a été imposé dans le projet car il répond à la problématique d'ordre total. En effet, l'objet réseau introduisant un temps de latence, cela implique que les messages ont pour obligation d'être traités dans l'ordre de leurs émissions, c'est à dire que si nous avons une sortie sur une porte, toutes les autres portes doivent être informées en même temps afin de garantir un état cohérent dans le système. L'ordre total n'a pas de lien avec l'ordre FIFO et l'ordre causal : il est à la fois plus fort (ordre total des messages délivrés) et plus fiable (aucun lien entre l'ordre de diffusions et l'ordre de délivrance).
  
\subsubsection*{Trace d'exécution commentée}
Une trace d'exécution commentée mettant évidence la gestion de concurrence pour cet algorithme est en annexe \ref{ABCast_log}.

\section{Conclusion }
Nous avons eu l'occasion de voir plusieurs algorithmes distribués dans ce projet. Il nous a ainsi permis de comprendre les enjeux de l'algorithmique distribuée et la complexité que peut avoir la mise en place d'algorithmes lorsque les données et les calculs sont partagés à plusieurs endroits.

\medskip
Parmi, les algorithmes que nous avons implémenté, nous avons pu constater qu'utiliser un jeton pour l'accès à une section critique ne peut s'adapter aux situations où l'équité est est une contrainte à respecter. Un algorithme distribué utilisant un jeton assure néanmoins la sûreté et la vivacité.

Les algorithmes avec des horloges logiques garantissent l'équité car c'est celui qui fait la demande à une section critique qui se verra attribuée celle-ci.
Toutefois la difficulté reste avec les demandes concurrentes. Ils garantissent aussi la sûreté et la vivacité.

Enfin, l'algorithme ABCast est d'ordre total et nous avons pu le remarquer que lorsqu'un message est distribué sur un processus, il en est de même sur tous les autres. En effet, dans un groupe, tous les processus délivrent les messages dans le même ordre, quelque soit l'ordre d'émission des messages.

\medskip
Tous ces algorithmes ont été adaptés afin de répondre aux exigences de notre gestion d'accès à un parking et les demandes concurrentes sont traitées selon les protocoles des algorithmes. 

\clearpage
\begin{huge}
\textbf{Annexes}
\end{huge}
\appendix

\section{Commentaire du log pour l'algorithme Naimi-Trehel}
\label{NT_log}
\textbf{Serveur de voitures}\\
\texttt{$[$SERVEUR\_VOITURES$]$ : Entree | Porte 2\\
$[$SERVEUR\_VOITURES$]$ : Sortie | Porte 3\\
$[$SERVEUR\_VOITURES$]$ : Entree | Porte 0\\
$[$SERVEUR\_VOITURES$]$ : Entree | Porte 2}\\
\emph{/* Considérons une partie du serveur de voitures où nous avons trois entrés et une sortie. Bien entendu, il y a eu des entrées et des sorties avant ces demandes. A noter que les demandes de jeton ne respecte pas l'odre du serveur de voitures. Cela est dû au temps de latence qu'introduit "Reso" dans les comminucations entre les portes. */}

\medskip
\textbf{Porte 0}\\
\texttt{$[$PORTE0$]$ <- 2 | REQ \\
$[$PORTE0$]$ -> 2 | Jeton\\
$[$PORTE0$]$ : Possession jeton : 2\\
$[$PORTE0$]$ : Entrée?\\
$[$PORTE0$]$ -> Owner : 2 | REQ\\
$[$PORTE0$]$ : Réception jeton | Places dispo : 0\\
$[$PORTE0$]$ : Entrée SC!\\
$[$PORTE0$]$ : Voiture refusée | Avant : 0 | Après : 0\\
$[$PORTE0$]$ : Sortie SC!\\
$[$PORTE0$]$ <- 3 | REQ \\
$[$PORTE0$]$ -> 3 | Jeton\\
$[$PORTE0$]$ : Possession jeton : 3}\\
\emph{/* La porte 0 avait reçu précédemment une demande de jeton de la porte 2. N'ayant pas demandé la SC, la porte 2 avait envoyé le jeton à celle ci (voir Log\_NT2.log). La porte 0 connaît maintenant son père qui est la porte 2. Pour les demandes du serveur, la porte porte 0 fait une demande de section critique à son père qui est la porte 2. Lors de la réception du jeton, nous pouvons voir qu'il n'y avait plus de places disponibles dans le parking. La voiture en demande d'entrée sur cette porte a donc été refusée. La porte 3 (voir Log\_NT3.log) fait en dernier une demande de jeton à la porte 0 car pour elle c'est son père dans l'arbre. */ }

\medskip
\textbf{Porte 1}\\
\texttt{$[$PORTE1$]$ <- 2 | REQ \\
$[$PORTE1$]$ -> 2 | Jeton\\
$[$PORTE1$]$ : Possession jeton : 2}

\medskip
\textbf{Porte 2}\\
\texttt{$[$PORTE2$]$ -> Owner : 0 | REQ} \emph{/* Envoi de demande de jeton à la porte 0 */}\\
\texttt{$[$PORTE2$]$ : Réception jeton | Places dispo : 1\\
$[$PORTE2$]$ : Entrée SC!\\
$[$PORTE2$]$ : Voiture entrée | Avant : 1 | Après : 0\\
$[$PORTE2$]$ : Sortie SC!\\
$[$PORTE2$]$ <- 3 | REQ \\
$[$PORTE2$]$ -> 3 | Jeton\\
$[$PORTE2$]$ : Possession jeton : 3\\
$[$PORTE2$]$ : Entrée?\\
$[$PORTE2$]$ -> Owner : 3 | REQ\\
$[$PORTE2$]$ : Réception jeton | Places dispo : 2\\
$[$PORTE2$]$ : Entrée SC!\\
$[$PORTE2$]$ : Voiture entrée | Avant : 2 | Après : 1\\
$[$PORTE2$]$ : Sortie SC!\\
$[$PORTE2$]$ : Entrée?} \emph{/* Reçoit une demande d'entrée d'une voiture */}\\
\texttt{$[$PORTE2$]$ : Entrée SC!\\
$[$PORTE2$]$ : Voiture entrée | Avant : 1 | Après : 0\\
$[$PORTE2$]$ : Sortie SC!\\
$[$PORTE2$]$ <- 0 | REQ} \emph{/* Jeton envoyé à la porte 0 */}\\
\texttt{$[$PORTE2$]$ -> 0 | Jeton} \emph{/* S'il s'agit d'une demande d'entrée sur la porte 0 (voir Log\_NT0.log), alors cette demande d'entrée de voiture sera refusée */}\\
\texttt{$[$PORTE2$]$ : Possession jeton : 0\\
$[$PORTE2$]$ <- 3 | REQ \\
$[$PORTE2$]$ -> 0 | REQ : 3\\
$[$PORTE2$]$ : Possession jeton : 3}\\
\emph{/* La porte 2 fera une demande de jeton à la porte 3 si une demande d'entrée ou de sortie de voitures est faite à cette porte. */}

\medskip
\textbf{Porte 3}\\
\texttt{$[$PORTE3$]$ <- 2 | REQ 
$[$PORTE3$]$ -> 0 | REQ : 2
$[$PORTE3$]$ : Possession jeton : 2
$[$PORTE3$]$ : Sortie?
$[$PORTE3$]$ -> Owner : 2 | REQ
$[$PORTE3$]$ : Réception jeton | Places dispo : 0
$[$PORTE3$]$ : Entrée SC!
$[$PORTE3$]$ : Voiture sortie | Avant : 0 | Après : 1
$[$PORTE3$]$ : Sortie SC!}
\emph{/* Sur la porte 3, nous pouvons constater que la porte 2 a fait une demande de jeton à la porte 3. Ne possédant pas le jeton, celle ci a renvoyé cette requête à son père qui est la porte 0 et a mis à jour son nouveau père. Lors d'une demande de jeton, la porte 3 fera une demande de jeton à la porte 2 (chose que nous pouvons constater dans cet exemple). */}


\section{Commentaire du log pour l'algorithme Carvalho et Roucairol}
\label{CR_log}
\texttt{Identité de la porte : 0\\
Initialisation des données de la porte\\
Envoie : 0 -> 1 | REQ | entrée | H = 1\\
Envoie : 0 -> 2 | REQ | entrée | H = 1\\
Envoie : 0 -> 3 | REQ | entrée | H = 1\\
Reçoit : 1 -> 0 | REQ | entrée | H = 1\\
Reçoit : 3 -> 0 | REQ | entrée | H = 1}\\
\emph{/* La porte 0 reçoit une demande d'entrée, les portes 1 et 3 également. La porte 0 est la première à traiter la demande d'entrée. Les porte 1 et 3 lui envoie un REQ mais sont en attente le temps que la porte 0 est en section critique */}\\
\texttt{Reçoit : 0 | REL\\
Reçoit : 0 | REL\\
Reçoit : 0 | REL\\
Porte 0 entre en section critique | entrée | places libres = 4\\
Envoie : 0 -> 1 | REL + UPDATE | entrée | H = 1\\
Envoie : 0 -> 2 | REL + UPDATE | entrée | H = 1\\
Envoie : 0 -> 3 | REL + UPDATE | entrée | H = 1}\\
\emph{/* La porte 0 a fini sa section critique, elle envoie les requêtes REL + UPDATE à ses voisins pour les informer et qu'ils se mettent à jour sur le nombre de places libres */}\\
\texttt{Reçoit : 1 -> 0 | REL + UPDATE | entrée | places libres = 3\\
Reçoit : 3 -> 0 | REL + UPDATE | entrée | places libres = 2}\\
\emph{/* Les portes 1 puis 3 ont ensuite chacune leur tour eu la section critique, puis envoyé à leur voisin, dont la porte 0, une requête REL + UPDATE. La porte 0 met à jour en conséquent son nombre de places libres */}


\section{Commentaire du log pour l'algorithme ABCast}
\label{ABCast_log}
\textbf{Serveur de voiture}\\
\texttt{$[$SERVEUR\_VOITURES$]$ : Entree | Porte 0\\
$[$SERVEUR\_VOITURES$]$ : Entree | Porte 2\\
$[$SERVEUR\_VOITURES$]$ : Entree | Porte 3}\\
\emph{/* Trois entrées simultanément sur les portes 0, 2 et 3. Les messages sont délivrés dans le même ordre sur toutes les portes. Les odres sont 0 2 3, 2 0 3, 3 0 2, 2 3 0, 0 3 2 et 3 2 0. */}

\medskip
\textbf{Porte 0}\\
\texttt{$[$PORTE0$]$ : Envoi diffusion | Type : 0 | Estampille locale : 1\\
$[$PORTE0$]$ <- Message diffusion | ID : 1.3\\
$[$PORTE0$]$ -> 3 | ACK\\
$[$PORTE0$]$ <- Message diffusion | ID : 1.2\\
$[$PORTE0$]$ -> 2 | ACK\\
$[$PORTE0$]$ <- Réception ACK | Message origine : 1.0 | Val ACK : 3.1\\
$[$PORTE0$]$ <- Message diffusion | ID : 1.0\\
$[$PORTE0$]$ -> 0 | ACK\\
$[$PORTE0$]$ <- Réception ACK | Message origine : 1.0 | Val ACK : 3.3\\
$[$PORTE0$]$ <- Message diffusion | ID : 5.3\\
$[$PORTE0$]$ -> 3 | ACK\\
$[$PORTE0$]$ <- Message diffusion | ID : 5.2\\
$[$PORTE0$]$ -> 2 | ACK\\
$[$PORTE0$]$ <- Message diffusion | ID : 4.1\\
$[$PORTE0$]$ -> 1 | ACK\\
$[$PORTE0$]$ <- Réception ACK | Message origine : 1.0 | Val ACK : 4.2\\
$[$PORTE0$]$ <- Diffusion Finale | Msg : 1.2\\
$[$PORTE0$]$ <- Réception ACK | Message origine : 1.0 | Val ACK : 5.0\\
$[$PORTE0$]$ : Diffusion Finale | Val finale : 5.0 | ID Msg : 1.0\\
$[$PORTE0$]$ <- Diffusion Finale | Msg : 1.3\\
$[$PORTE0$]$ : Voiture entrée | Autre porte : 2 | Avant : 5 | Après : 4} \emph{/* Message délivré sur la porte 2 */}\\
\texttt{$[$PORTE0$]$ <- Message diffusion | ID : 8.1\\
$[$PORTE0$]$ -> 1 | ACK\\
$[$PORTE0$]$ <- Diffusion Finale | Msg : 1.0\\
$[$PORTE0$]$ : Voiture entrée | Avant : 4 | Après : 3} \emph{/* Message délivré sur cette porte */}\\
\texttt{$[$PORTE0$]$ : Voiture entrée | Autre porte : 3 | Avant : 3 | Après : 2} \emph{/* Message délivré sur la porte 3 */\\
/* Comme mentionné dans le serveur de voitures, les messages sont diffusés dans le même ordre. Dans notre cas, sur la porte 0, nous avons la délivrance de messages dans l'ordre 2 0 3. */}

\medskip
\textbf{Porte 1}\\
\texttt{$[$PORTE1$]$ <- Message diffusion | ID : 1.2\\
$[$PORTE1$]$ -> 2 | ACK\\
$[$PORTE1$]$ <- Message diffusion | ID : 1.0\\
$[$PORTE1$]$ -> 0 | ACK\\
$[$PORTE1$]$ <- Message diffusion | ID : 1.3\\
$[$PORTE1$]$ -> 3 | ACK\\
$[$PORTE1$]$ : Envoi diffusion | Type : 1 | Estampille locale : 4\\
$[$PORTE1$]$ <- Message diffusion | ID : 4.1\\
$[$PORTE1$]$ -> 1 | ACK\\
$[$PORTE1$]$ <- Réception ACK | Message origine : 4.1 | Val ACK : 8.0\\
$[$PORTE1$]$ <- Réception ACK | Message origine : 4.1 | Val ACK : 6.1\\
$[$PORTE1$]$ <- Diffusion Finale | Msg : 1.2\\
$[$PORTE1$]$ <- Message diffusion | ID : 5.3\\
$[$PORTE1$]$ -> 3 | ACK\\
$[$PORTE1$]$ <- Réception ACK | Message origine : 4.1 | Val ACK : 9.3\\
$[$PORTE1$]$ <- Message diffusion | ID : 5.2\\
$[$PORTE1$]$ -> 2 | ACK\\
$[$PORTE1$]$ <- Diffusion Finale | Msg : 1.0\\
$[$PORTE1$]$ : Envoi diffusion | Type : 1 | Estampille locale : 8\\
$[$PORTE1$]$ <- Message diffusion | ID : 8.1\\
$[$PORTE1$]$ -> 1 | ACK\\
$[$PORTE1$]$ <- Diffusion Finale | Msg : 1.3\\
$[$PORTE1$]$ : Voiture entrée | Autre porte : 2 | Avant : 5 | Après : 4} \emph{/* Porte 2 */}\\
\texttt{$[$PORTE1$]$ : Voiture entrée | Autre porte : 0 | Avant : 4 | Après : 3}  \emph{/* Porte 0 */}\\
\texttt{$[$PORTE1$]$ : Voiture entrée | Autre porte : 3 | Avant : 3 | Après : 2}  \emph{/* Porte 3 */\\
/* Sur la porte 1, nous avons également la délivrance de messages dans l'ordre : 2 0 3. */}

\medskip
\textbf{Porte 2}\\
\texttt{$[$PORTE2$]$ : Envoi diffusion | Type : 0 | Estampille locale : 1\\
$[$PORTE2$]$ <- Message diffusion | ID : 1.2\\
$[$PORTE2$]$ -> 2 | ACK\\
$[$PORTE2$]$ <- Réception ACK | Message origine : 1.2 | Val ACK : 4.0\\
$[$PORTE2$]$ <- Réception ACK | Message origine : 1.2 | Val ACK : 2.1\\
$[$PORTE2$]$ <- Message diffusion | ID : 1.0\\
$[$PORTE2$]$ -> 0 | ACK\\
$[$PORTE2$]$ <- Réception ACK | Message origine : 1.2 | Val ACK : 4.3\\
$[$PORTE2$]$ <- Message diffusion | ID : 1.3\\
$[$PORTE2$]$ -> 3 | ACK\\
$[$PORTE2$]$ : Envoi diffusion | Type : 1 | Estampille locale : 5\\
$[$PORTE2$]$ <- Message diffusion | ID : 5.3\\
$[$PORTE2$]$ -> 3 | ACK\\
$[$PORTE2$]$ <- Message diffusion | ID : 5.2\\
$[$PORTE2$]$ -> 2 | ACK\\
$[$PORTE2$]$ <- Réception ACK | Message origine : 1.2 | Val ACK : 3.2\\
$[$PORTE2$]$ : Diffusion Finale | Val finale : 4.3 | ID Msg : 1.2\\
$[$PORTE2$]$ <- Réception ACK | Message origine : 5.2 | Val ACK : 8.2\\
$[$PORTE2$]$ <- Message diffusion | ID : 4.1\\
$[$PORTE2$]$ -> 1 | ACK\\
$[$PORTE2$]$ <- Réception ACK | Message origine : 5.2 | Val ACK : 7.3\\
$[$PORTE2$]$ : Envoi diffusion | Type : 1 | Estampille locale : 9\\
$[$PORTE2$]$ <- Diffusion Finale | Msg : 1.2\\
$[$PORTE2$]$ <- Réception ACK | Message origine : 5.2 | Val ACK : 7.0\\
$[$PORTE2$]$ <- Diffusion Finale | Msg : 1.3\\
$[$PORTE2$]$ <- Message diffusion | ID : 9.2\\
$[$PORTE2$]$ -> 2 | ACK\\
$[$PORTE2$]$ <- Message diffusion | ID : 8.1\\
$[$PORTE2$]$ -> 1 | ACK\\
$[$PORTE2$]$ <- Diffusion Finale | Msg : 1.0\\
$[$PORTE2$]$ : Voiture entrée | Avant : 5 | Après : 4} \emph{/* Message délivré sur cette porte */}\\
\texttt{$[$PORTE2$]$ : Voiture entrée | Autre porte : 0 | Avant : 4 | Après : 3} \emph{/* Message délivré sur la porte 0 */}\\
\texttt{$[$PORTE2$]$ : Voiture entrée | Autre porte : 3 | Avant : 3 | Après : 2} \emph{/* Message délivré sur la porte 3 */\\
/* Délivrance de messages dans l'ordre 2 0 3. */}

\medskip
\textbf{Porte 3}\\
\texttt{$[$PORTE3$]$ : Envoi diffusion | Type : 0 | Estampille locale : 1\\
$[$PORTE3$]$ <- Message diffusion | ID : 1.0\\
$[$PORTE3$]$ -> 0 | ACK\\
$[$PORTE3$]$ <- Réception ACK | Message origine : 1.3 | Val ACK : 3.0\\
$[$PORTE3$]$ <- Message diffusion | ID : 1.2\\
$[$PORTE3$]$ -> 2 | ACK\\
$[$PORTE3$]$ <- Message diffusion | ID : 1.3\\
$[$PORTE3$]$ -> 3 | ACK\\
$[$PORTE3$]$ <- Réception ACK | Message origine : 1.3 | Val ACK : 4.1\\
$[$PORTE3$]$ : Envoi diffusion | Type : 0 | Estampille locale : 5\\
$[$PORTE3$]$ <- Réception ACK | Message origine : 1.3 | Val ACK : 5.3\\
$[$PORTE3$]$ <- Message diffusion | ID : 5.2\\
$[$PORTE3$]$ -> 2 | ACK\\
$[$PORTE3$]$ <- Réception ACK | Message origine : 5.3 | Val ACK : 7.2\\
$[$PORTE3$]$ <- Réception ACK | Message origine : 1.3 | Val ACK : 5.2\\
$[$PORTE3$]$ : Diffusion Finale | Val finale : 5.3 | ID Msg : 1.3\\
$[$PORTE3$]$ <- Message diffusion | ID : 5.3\\
$[$PORTE3$]$ -> 3 | ACK\\
$[$PORTE3$]$ <- Réception ACK | Message origine : 5.3 | Val ACK : 8.3\\
$[$PORTE3$]$ <- Message diffusion | ID : 4.1\\
$[$PORTE3$]$ -> 1 | ACK\\
$[$PORTE3$]$ <- Réception ACK | Message origine : 5.3 | Val ACK : 6.0\\
$[$PORTE3$]$ <- Diffusion Finale | Msg : 1.0\\
$[$PORTE3$]$ <- Diffusion Finale | Msg : 1.3\\
$[$PORTE3$]$ <- Diffusion Finale | Msg : 1.2\\
$[$PORTE3$]$ : Voiture entrée | Autre porte : 2 | Avant : 5 | Après : 4} \emph{/* Message délivré sur la porte 2 */}\\
\texttt{$[$PORTE3$]$ : Voiture entrée | Autre porte : 0 | Avant : 4 | Après : 3} \emph{/* Message délivré sur la porte 0 */}\\
\texttt{$[$PORTE3$]$ : Voiture entrée | Avant : 3 | Après : 2} \emph{/* Message délivré sur la porte 3 */\\
/* Message également délivré dans l'odre que les autres portes, ordre 2 0 3. */ }


\end{document}